#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;


 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
    //首先跑一个层次遍历
    string result = "";
    queue<TreeNode*> Q;
    if(root == NULL){
        return result;
    }
    result += '[';
    Q.push(root);
    while (!Q.empty())
    {
        TreeNode* temp = Q.front();
        Q.pop();
        if(temp!=NULL){
            result =result+to_string(temp->val)+',';
            Q.push(temp->left);
            Q.push(temp->right);
        }
        else{
            result += "null,";
        }
    }
    //取出结尾多余的NULL
    while(string(result.begin()+result.size()-5,result.end())=="null,"){
        result.erase(result.size()-5,5);
    }
    result.back()= ']';
    return result;    
}

    

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data=="[]"){
            return ;
        }
        //先处理一下字符串
        string tempData(data.begin()+1,data.end()-1);
        
        vector<string> Q;
        string temp = "";
        for(int i = 0;i<tempData.size();++i){
            if(tempData[i]!=','){
                temp += tempData[i];
            }
            else{
                Q.push_back(temp);
                temp = "";
            }
        }
        Q.push_back(temp);
        return func(Q);

    }

    TreeNode* func(vector<string>& Q){
       if(Q.empty()){
           return NULL;
       }
       for(int i = 0;i<Q.size();++i){
           if(i==0&&Q[i]!="null"){
               TreeNode* head = new TreeNode(stoi(Q[i]));
               M.insert(make_pair(i+1,head));
           }
           else if(i!=0&&Q[i]!="null"){
               TreeNode* tempNode = new TreeNode(stoi(Q[i]));
               M.insert(make_pair(i+1,tempNode));
               if((i+1)%2==0){
                   M[(i+1)/2]->left = tempNode;
               }
               else{
                   M[(i+1)/2]->right = tempNode;
               }
           }
       }
       return M[1];
    }
public:
    map<int,TreeNode*> M;
};

int main(){
    Codec S;
    TreeNode* head = new TreeNode(1);
    head->left = new TreeNode(2);
    // head->right = new TreeNode(3);
    // head->right->left = new TreeNode(4);
    // head->right->right = new TreeNode(5);
    string result = S.serialize(head);
    TreeNode* T = S.deserialize(result);
    return 0;
}